home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 3 / Amiga Tools 3.iso / grafik / raytracing / rayshade-4.0.6.3 / raypaint / render.c < prev    next >
C/C++ Source or Header  |  1994-08-09  |  18KB  |  706 lines
  1. /*
  2.  * render.c
  3.  *
  4.  * Copyright (C) 1989, 1991 Craig E. Kolb, Rod G. Bogart
  5.  *
  6.  * This software may be freely copied, modified, and redistributed
  7.  * provided that this copyright notice is preserved on all copies.
  8.  *
  9.  * You may not distribute this software, in whole or in part, as part of
  10.  * any commercial product without the express consent of the authors.
  11.  * 
  12.  * There is no warranty or other guarantee of fitness of this software
  13.  * for any purpose.  It is provided solely "as is".
  14.  *
  15.  * render.c,v 4.1 1994/08/09 08:06:25 explorer Exp
  16.  *
  17.  * render.c,v
  18.  * Revision 4.1  1994/08/09  08:06:25  explorer
  19.  * Bump version to 4.1
  20.  *
  21.  * Revision 1.1.1.1  1994/08/08  04:52:27  explorer
  22.  * Initial import.  This is a prerelease of 4.0.6enh3, or 4.1 possibly.
  23.  *
  24.  * Revision 4.0  91/07/17  17:37:09  kolb
  25.  * Initial version.
  26.  * 
  27.  */
  28.  
  29. #include "rayshade.h"
  30. #include "libcommon/sampling.h"
  31. #include "libsurf/atmosphere.h"
  32. #include "viewing.h"
  33. #include "options.h"
  34. #include "stats.h"
  35. #include "picture.h"
  36.  
  37. /*
  38.  * "Dither matrices" used to encode the 'number' of a ray that samples a
  39.  * particular portion of a pixel.  Hand-coding is ugly, but...
  40.  */
  41. static int        *SampleNumbers;
  42. static int OneSample[1] =     {0};
  43. static int TwoSamples[4] =    {0, 2,
  44.                  3, 1};
  45. static int ThreeSamples[9] =    {0, 2, 7,
  46.                  6, 5, 1,
  47.                  3, 8, 4};
  48. static int FourSamples[16] =    { 0,  8,  2, 10,
  49.                  12,  4, 14,  6,
  50.                   3, 11,  1,  9,
  51.                  15,  7, 13,  5};
  52. static int FiveSamples[25] =    { 0,  8, 23, 17,  2,
  53.                  19, 12,  4, 20, 15,
  54.                   3, 21, 16,  9,  6,
  55.                  14, 10, 24,  1, 13,
  56.                  22,  7, 18, 11,  5};
  57. static int SixSamples[36] =    { 6, 32,  3, 34, 35,  1,
  58.                   7, 11, 27, 28,  8, 30,
  59.                  24, 14, 16, 15, 23, 19,
  60.                  13, 20, 22, 21, 17, 18,
  61.                  25, 29, 10,  9, 26, 12,
  62.                  36,  5, 33,  4,  2, 31};
  63. static int SevenSamples[49] =    {22, 47, 16, 41, 10, 35,  4,
  64.                   5, 23, 48, 17, 42, 11, 29,
  65.                  30,  6, 24, 49, 18, 36, 12,
  66.                  13, 31,  7, 25, 43, 19, 37,
  67.                  38, 14, 32,  1, 26, 44, 20,
  68.                  21, 39,  8, 33,  2, 27, 45,
  69.                  46, 15, 40,  9, 34,  3, 28};
  70. static int EightSamples[64] =    { 8, 58, 59,  5,  4, 62, 63,  1,
  71.                  49, 15, 14, 52, 53, 11, 10, 56,
  72.                  41, 23, 22, 44, 45, 19, 18, 48,
  73.                  32, 34, 35, 29, 28, 38, 39, 25,
  74.                  40, 26, 27, 37, 36, 30, 31, 33,
  75.                  17, 47, 46, 20, 21, 43, 42, 24,
  76.                   9, 55, 54, 12, 13, 51, 50, 16,
  77.                  64,  2,  3, 61, 60,  6,  7, 57};
  78. #define RFAC    0.299
  79. #define GFAC    0.587
  80. #define BFAC    0.114
  81.  
  82. #define NOT_CLOSED 0
  83. #define CLOSED_PARTIAL   1
  84. #define CLOSED_SUPER 2
  85. /*
  86.  * If a region has area < MINAREA, it is considered to be "closed",
  87.  * (a permanent leaf).  Regions that meet this criterion
  88.  * are drawn pixel-by-pixel rather.
  89.  */
  90. #define MINAREA        9
  91.  
  92. #define SQ_AREA(s)    (((s)->xsize+1)*((s)->ysize+1))
  93.  
  94. #define PRIORITY(s)    ((s)->var * SQ_AREA(s))
  95.  
  96. #define INTENSITY(p)    ((RFAC*(p)[0] + GFAC*(p)[1] + BFAC*(p)[2])/255.)
  97.  
  98. #define OVERLAPS_RECT(s) (!Rectmode || \
  99.                 ((s)->xpos <= Rectx1 && \
  100.                  (s)->ypos <= Recty1 && \
  101.                  (s)->xpos+(s)->xsize >= Rectx0 && \
  102.                  (s)->ypos+(s)->ysize >= Recty0))
  103.  
  104. typedef unsigned char RGB[3];
  105.  
  106. static RGB **Image;
  107. static char **SampleMap;
  108.  
  109. /*
  110.  * Sample square
  111.  */
  112. typedef struct SSquare {
  113.     short xpos, ypos, xsize, ysize;
  114.     short depth;
  115.     short leaf, closed;
  116.     float mean, var, prio;
  117.     struct SSquare *child[4], *parent;
  118. } SSquare;
  119.  
  120. SSquare *SSquares, *SSquareCreate(), *SSquareInstall(), *SSquareSelect(),
  121.     *SSquareFetchAtMouse();
  122.  
  123. Float SSquareComputeLeafVar();
  124.  
  125. Ray    TopRay;                /* Top-level ray. */
  126. int    Rectmode = FALSE,
  127.     Rectx0, Recty0, Rectx1, Recty1;
  128. int    SuperSampleMode = 0;
  129. #define SSCLOSED (SuperSampleMode + 1)
  130.  
  131. Render(argc, argv, gray)
  132. int argc;
  133. char **argv;
  134. int gray;
  135. {
  136.     /*
  137.      * Do an adaptive trace, displaying results in a
  138.      * window as we go.
  139.      */
  140.     SSquare *cursq;
  141.     Pixel *pixelbuf;
  142.     int y, x;
  143.  
  144.     /*
  145.      * The top-level ray TopRay always has as its origin the
  146.      * eye position and as its medium NULL, indicating that it
  147.      * is passing through a medium with index of refraction
  148.      * equal to DefIndex.
  149.      */
  150.     TopRay.pos = Camera.pos;
  151.     TopRay.media = (Medium *)0;
  152.     TopRay.depth = 0;
  153.     /*
  154.      * Doesn't handle motion blur yet.
  155.      */
  156.     TopRay.time = Options.framestart;
  157.  
  158.     GraphicsInit(Screen.xsize, Screen.ysize, "rayview", gray);
  159.     /*
  160.      * Allocate array of samples.
  161.      */
  162.     Image=(RGB **)Malloc(Screen.ysize*sizeof(RGB *));
  163.     SampleMap = (char **)Malloc(Screen.ysize * sizeof(char *));
  164.     for (y = 0; y < Screen.ysize; y++) {
  165.         Image[y]=(RGB *)Calloc(Screen.xsize, sizeof(RGB));
  166.         SampleMap[y] = (char *)Calloc(Screen.xsize, sizeof(char));
  167.     }
  168.     switch (Sampling.sidesamples) {
  169.         case 1:
  170.             SampleNumbers = OneSample;
  171.             break;
  172.         case 2:
  173.             SampleNumbers = TwoSamples;
  174.             break;
  175.         case 3:
  176.             SampleNumbers = ThreeSamples;
  177.             break;
  178.         case 4:
  179.             SampleNumbers = FourSamples;
  180.             break;
  181.         case 5:
  182.             SampleNumbers = FiveSamples;
  183.             break;
  184.         case 6:
  185.             SampleNumbers = SixSamples;
  186.             break;
  187.         case 7:
  188.             SampleNumbers = SevenSamples;
  189.             break;
  190.         case 8:
  191.             SampleNumbers = EightSamples;
  192.             break;
  193.         default:
  194.             RLerror(RL_PANIC,
  195.                 "Sorry, %d rays/pixel not supported.\n",
  196.                     Sampling.totsamples);
  197.     }
  198.     /*
  199.      * Take initial four samples
  200.      */
  201.     SSquareSample(0, 0, FALSE);
  202.     SSquareSample(Screen.xsize -1, 0, FALSE);
  203.     SSquareSample(Screen.xsize -1, Screen.ysize -1, FALSE);
  204.     SSquareSample(0, Screen.ysize -1, FALSE);
  205.     SSquares = SSquareInstall(0, 0, Screen.xsize -1, Screen.ysize -1,
  206.                   0, (SSquare *) NULL);
  207.  
  208.     for (y = 1; y <= 5; y++) {
  209.         /*
  210.          * Create and draw every region at depth y.
  211.          */
  212.         SSquareDivideToDepth(SSquares, y);
  213.     }
  214.         
  215.  
  216.     while ((cursq = SSquareSelect(SSquares)) != (SSquare *)NULL) {
  217.         SSquareDivide(cursq);
  218.         if (GraphicsRedraw())
  219.             SSquareDraw(SSquares);
  220.         if (GraphicsMiddleMouseEvent()) 
  221.             SSetRectMode();
  222.     }
  223.  
  224.     /*
  225.      * Finished the image; write to image file.
  226.      */
  227.     pixelbuf = (Pixel *)Malloc(Screen.xsize * sizeof(Pixel));
  228.     PictureStart(argv);
  229.     for (y = 0; y < Screen.ysize; y++) {
  230.         /*
  231.          * This is really disgusting.
  232.          */
  233.         for (x = 0; x < Screen.xsize; x++) {
  234.             pixelbuf[x].r = Image[y][x][0] / 255.;
  235.             pixelbuf[x].g = Image[y][x][1] / 255.;
  236.             pixelbuf[x].b = Image[y][x][2] / 255.;
  237.             pixelbuf[x].alpha = SampleMap[y][x];
  238.         }
  239.         PictureWriteLine(pixelbuf);
  240.     }
  241.     PictureEnd();
  242.     free((voidstar)pixelbuf);
  243. }
  244.  
  245. Float
  246. SampleTime(sampnum)
  247. int sampnum;
  248. {
  249.     Float window, jitter = 0.0, res;
  250.  
  251.     if (Options.shutterspeed <= 0.)
  252.         return Options.framestart;
  253.     if (Options.jitter)
  254.         jitter = nrand();
  255.     window = Options.shutterspeed / Sampling.totsamples;
  256.     res = Options.framestart + window * (sampnum + jitter);
  257.     TimeSet(res);
  258.     return res;
  259. }
  260.  
  261. SSetRectMode()
  262. {
  263.     int x1,y1,x2,y2;
  264.  
  265.     if (Rectmode) {
  266.         Rectmode = FALSE;
  267.         RecomputePriority(SSquares);
  268.     }
  269.     GraphicsGetMousePos(&x1, &y1);
  270.     while (GraphicsMiddleMouseEvent())
  271.         ;
  272.     GraphicsGetMousePos(&x2, &y2);
  273.     if (x1 < x2) {
  274.         Rectx0 = (x1 < 0) ? 0 : x1;
  275.         Rectx1 = (x2 >= Screen.xsize) ? Screen.xsize - 1 : x2;
  276.     } else {
  277.         Rectx0 = (x2 < 0) ? 0 : x2;
  278.         Rectx1 = (x1 >= Screen.xsize) ? Screen.xsize - 1 : x1;
  279.     } if (y1 < y2) {
  280.         Recty0 = (y1 < 0) ? 0 : y1;
  281.         Recty1 = (y2 >= Screen.ysize) ? Screen.ysize - 1 : y2;
  282.     } else {
  283.         Recty0 = (y2 < 0) ? 0 : y2;
  284.         Recty1 = (y1 >= Screen.ysize) ? Screen.ysize - 1 : y1;
  285.     }
  286.     Rectmode = TRUE;
  287.     /* setup current rect */
  288.     (void)RecomputePriority(SSquares);
  289. }
  290.  
  291. RecomputePriority(sq)
  292. SSquare *sq;
  293. {
  294.     Float maxp;
  295.  
  296.     if (!OVERLAPS_RECT(sq)) {
  297.         sq->closed = SSCLOSED;
  298.         return FALSE;
  299.     }
  300.  
  301.     if (sq->leaf) {
  302.         if (SQ_AREA(sq) >= MINAREA)
  303.             sq->closed = NOT_CLOSED;
  304.         return TRUE;
  305.     }
  306.     maxp = 0.;
  307.     if (RecomputePriority(sq->child[0]))
  308.         maxp = max(maxp, sq->child[0]->prio);
  309.     if (RecomputePriority(sq->child[1]))
  310.         maxp = max(maxp, sq->child[1]->prio);
  311.     if (RecomputePriority(sq->child[2]))
  312.         maxp = max(maxp, sq->child[2]->prio);
  313.     if (RecomputePriority(sq->child[3]))
  314.         maxp = max(maxp, sq->child[3]->prio);
  315.     sq->prio = maxp;
  316. #if 0
  317.     if ((sq->child[0]->closed == CLOSED_SUPER) &&
  318.         (sq->child[1]->closed == CLOSED_SUPER) &&
  319.         (sq->child[2]->closed == CLOSED_SUPER) &&
  320.         (sq->child[3]->closed == CLOSED_SUPER))
  321.         sq->closed = CLOSED_SUPER;
  322.     else if (sq->child[0]->closed && sq->child[1]->closed &&
  323.          sq->child[2]->closed && sq->child[3]->closed)
  324.         sq->closed = CLOSED_PARTIAL;
  325.     else
  326.         sq->closed = NOT_CLOSED;
  327. #else
  328.     if ((sq->child[0]->closed >= SSCLOSED) &&
  329.         (sq->child[1]->closed >= SSCLOSED) &&
  330.         (sq->child[2]->closed >= SSCLOSED) &&
  331.         (sq->child[3]->closed >= SSCLOSED))
  332.         sq->closed = SSCLOSED;
  333.     else
  334.         sq->closed = NOT_CLOSED;
  335. #endif
  336.     return TRUE;
  337. }
  338.  
  339. SSquareSample(x, y, supersample)
  340. int x, y, supersample;
  341. {
  342.     Float upos, vpos, u, v;
  343.     int xx, yy, xp, sampnum, usamp, vsamp;
  344.     Pixel ctmp;
  345.     Pixel p;
  346.     extern unsigned char correct();
  347.  
  348.     if (SampleMap[y][x] >= 128 + supersample)
  349.         /* already a sample there */
  350.         return;
  351.     SampleMap[y][x] = 128 + supersample;
  352.     if (supersample) {
  353.         p.r = p.g = p.b = p.alpha = 0;
  354.         sampnum = 0;
  355.         xp = x + Screen.minx;
  356.         vpos = Screen.miny + y - 0.5*Sampling.filterwidth;
  357.         for (yy = 0; yy < Sampling.sidesamples; yy++,
  358.              vpos += Sampling.filterdelta) {
  359.             upos = xp - 0.5*Sampling.filterwidth;
  360.             for (xx = 0; xx < Sampling.sidesamples; xx++,
  361.                  upos += Sampling.filterdelta) {
  362.                 if (Options.jitter) {
  363.                     u = upos + nrand()*Sampling.filterdelta;
  364.                     v = vpos + nrand()*Sampling.filterdelta;
  365.                 } else {
  366.                     u = upos;
  367.                     v = vpos;
  368.                 }
  369.                 TopRay.time = SampleTime(SampleNumbers[sampnum]);
  370.                 SampleScreen(u, v, &TopRay, &ctmp,
  371.                          SampleNumbers[sampnum]);
  372.                 p.r += ctmp.r*Sampling.filter[xx][yy];
  373.                 p.g += ctmp.g*Sampling.filter[xx][yy];
  374.                 p.b += ctmp.b*Sampling.filter[xx][yy];
  375.                 if (++sampnum == Sampling.totsamples)
  376.                     sampnum = 0;
  377.             }
  378.         }
  379.     }
  380.     else {
  381.         sampnum = nrand() * Sampling.totsamples;
  382.         usamp = sampnum % Sampling.sidesamples;
  383.         vsamp = sampnum / Sampling.sidesamples;
  384.  
  385.         vpos = Screen.miny + y - 0.5*Sampling.filterwidth
  386.             + vsamp * Sampling.filterdelta;
  387.         upos = x + Screen.minx - 0.5*Sampling.filterwidth +
  388.                 usamp*Sampling.filterdelta;
  389.         if (Options.jitter) {
  390.             vpos += nrand()*Sampling.filterdelta;
  391.             upos += nrand()*Sampling.filterdelta;
  392.         }
  393.         TopRay.time = SampleTime(SampleNumbers[sampnum]);
  394.         SampleScreen(upos, vpos, &TopRay, &p, SampleNumbers[sampnum]);
  395.     }
  396.     Image[y][x][0] = CORRECT(p.r);
  397.     Image[y][x][1] = CORRECT(p.g);
  398.     Image[y][x][2] = CORRECT(p.b);
  399. }
  400.  
  401. SSquare *
  402. SSquareCreate(xp, yp, xs, ys, d, parent)
  403. int xp, yp, xs, ys, d;
  404. SSquare *parent;
  405. {
  406.     SSquare *new;
  407.     Float i1, i2, i3, i4;
  408.  
  409.     new = (SSquare *)Calloc(1, sizeof(SSquare));
  410.     new->xpos = xp; new->ypos = yp;
  411.     new->xsize = xs; new->ysize = ys;
  412.     new->depth = d;
  413.     new->parent = parent;
  414.     i1 = INTENSITY(Image[new->ypos][new->xpos]);
  415.     i2 = INTENSITY(Image[new->ypos+new->ysize][new->xpos]);
  416.     i3 = INTENSITY(Image[new->ypos+new->ysize][new->xpos+new->xsize]);
  417.     i4 = INTENSITY(Image[new->ypos][new->xpos+new->xsize]);
  418.     new->mean = 0.25 * (i1+i2+i3+i4);
  419.     if (SQ_AREA(new) < MINAREA) {
  420.         new->prio = 0;
  421.         new->closed = SSCLOSED;
  422.     } else {
  423.         new->var = SSquareComputeLeafVar(new, i1, i2, i3, i4);
  424.         new->prio = PRIORITY(new);
  425.         new->closed = NOT_CLOSED;
  426.     }
  427.     new->leaf = TRUE;
  428.     return new;
  429. }
  430.  
  431. Float
  432. SSquareComputeLeafVar(sq, i1, i2, i3, i4)
  433. SSquare *sq;
  434. Float i1, i2, i3, i4;
  435. {
  436.     Float res, diff;
  437.  
  438.     diff = i1 - sq->mean;
  439.     res = diff*diff;
  440.     diff = i2 - sq->mean;
  441.     res += diff*diff;
  442.     diff = i3 - sq->mean;
  443.     res += diff*diff;
  444.     diff = i4 - sq->mean;
  445.     return res + diff*diff;
  446. }
  447.  
  448. SSquareDivideToDepth(sq, d)
  449. SSquare *sq;
  450. int d;
  451. {
  452.     if (sq->depth == d)
  453.         return;
  454.     if (sq->leaf)
  455.         SSquareDivide(sq);
  456.     SSquareDivideToDepth(sq->child[0], d);
  457.     SSquareDivideToDepth(sq->child[1], d);
  458.     SSquareDivideToDepth(sq->child[2], d);
  459.     SSquareDivideToDepth(sq->child[3], d);
  460. }
  461.  
  462. SSquareDivide(sq)
  463. SSquare *sq;
  464. {
  465.     int lowx, lowy, midx, midy, hix, hiy;
  466.     int newxsize, newysize, ndepth, supersample;
  467.     /*
  468.      * Divide the square into fourths by tracing 12
  469.      * new samples if necessary.
  470.      */
  471.     newxsize = sq->xsize / 2;
  472.     newysize = sq->ysize / 2;
  473.     lowx = sq->xpos; lowy = sq->ypos;
  474.     midx = sq->xpos + newxsize;
  475.     midy = sq->ypos + newysize;
  476.     hix  = sq->xpos + sq->xsize;
  477.     hiy  = sq->ypos + sq->ysize;
  478.     ndepth = sq->depth + 1;
  479.     /* create new samples */
  480.     supersample = FALSE;
  481.     SSquareSample(midx, lowy, supersample);
  482.     SSquareSample(lowx, midy, supersample);
  483.     SSquareSample(midx, midy, supersample);
  484.     SSquareSample(hix,  midy, supersample);
  485.     SSquareSample(midx, hiy, supersample);
  486. #ifdef SHARED_EDGES
  487.     /* create and draw new squares */
  488.     sq->child[0] = SSquareInstall(lowx,lowy,newxsize,newysize,ndepth,sq);
  489.     sq->child[1] = SSquareInstall(midx, lowy, sq->xsize - newxsize,
  490.             newysize, ndepth,sq);
  491.     sq->child[2] = SSquareInstall(lowx, midy, newxsize,
  492.             sq->ysize - newysize, ndepth,sq);
  493.     sq->child[3] = SSquareInstall(midx, midy, sq->xsize - newxsize,
  494.              sq->ysize - newysize, ndepth,sq);
  495. #else
  496.     /*
  497.      *  draw additional samples in order to subdivide such that
  498.      * edges of regions do not overlap
  499.      */
  500.     SSquareSample(midx +1, lowy, supersample);
  501.     SSquareSample(midx +1, midy, supersample);
  502.     SSquareSample(lowx, midy +1, supersample);
  503.     SSquareSample(midx, midy +1, supersample);
  504.     SSquareSample(midx +1, midy +1, supersample);
  505.     SSquareSample(hix, midy +1, supersample);
  506.     SSquareSample(midx +1, hiy, supersample);
  507.  
  508.     /* create and draw new squares */
  509.     sq->child[0] = SSquareInstall(lowx,lowy,
  510.                 newxsize,newysize,ndepth,sq);
  511.     sq->child[1] = SSquareInstall(midx+1, lowy, sq->xsize - newxsize -1,
  512.             newysize, ndepth,sq);
  513.     sq->child[2] = SSquareInstall(lowx, midy+1, newxsize,
  514.             sq->ysize - newysize-1, ndepth,sq);
  515.     sq->child[3] = SSquareInstall(midx+1, midy+1, sq->xsize - newxsize-1,
  516.              sq->ysize - newysize-1, ndepth,sq);
  517. #endif
  518.     sq->leaf = FALSE;
  519.     /*
  520.      * Recompute parent's mean and variance.
  521.      */
  522.     if (OVERLAPS_RECT(sq))
  523.         SSquareRecomputeStats(sq);
  524. }
  525.  
  526. SSquareRecomputeStats(sq)
  527. SSquare *sq;
  528. {
  529.     Float maxp;
  530.     int in[4], closeflag;
  531.  
  532.     in[0] = OVERLAPS_RECT(sq->child[0]);
  533.     in[1] = OVERLAPS_RECT(sq->child[1]);
  534.     in[2] = OVERLAPS_RECT(sq->child[2]);
  535.     in[3] = OVERLAPS_RECT(sq->child[3]);
  536.  
  537.     if ((in[0] && (sq->child[0]->closed < SSCLOSED)) ||
  538.         (in[1] && (sq->child[1]->closed < SSCLOSED)) ||
  539.         (in[2] && (sq->child[2]->closed < SSCLOSED)) ||
  540.         (in[3] && (sq->child[3]->closed < SSCLOSED))) {
  541.         maxp = 0.;
  542.         if (in[0])
  543.             maxp = max(maxp, sq->child[0]->prio);
  544.         if (in[1])
  545.             maxp = max(maxp, sq->child[1]->prio);
  546.         if (in[2])
  547.             maxp = max(maxp, sq->child[2]->prio);
  548.         if (in[3])
  549.             maxp = max(maxp, sq->child[3]->prio);
  550.         sq->closed = NOT_CLOSED;
  551.         sq->prio = maxp;
  552.     } else if ((sq->child[0]->closed == CLOSED_SUPER) &&
  553.            (sq->child[1]->closed == CLOSED_SUPER) &&
  554.            (sq->child[2]->closed == CLOSED_SUPER) &&
  555.            (sq->child[3]->closed == CLOSED_SUPER)) {
  556.         sq->closed = CLOSED_SUPER;
  557.         sq->prio = 0;
  558. #if 0
  559.     } else if ((!in[0] || sq->child[0]->closed >= SSCLOSED) &&
  560.            (!in[1] || sq->child[1]->closed >= SSCLOSED) &&
  561.            (!in[2] || sq->child[2]->closed >= SSCLOSED) &&
  562.            (!in[3] || sq->child[3]->closed >= SSCLOSED)) {
  563.         sq->closed = SSCLOSED;
  564.         sq->prio = 0;
  565. #endif
  566.     } else {
  567.         sq->closed = SSCLOSED;
  568.         sq->prio = 0;
  569.     }
  570.     if (sq->parent)
  571.         SSquareRecomputeStats(sq->parent);
  572. }
  573.  
  574. SSquare *
  575. SSquareInstall(xp, yp, xs, ys, d, parent)
  576. int xp, yp, xs, ys, d;
  577. SSquare *parent;
  578. {
  579.     SSquare *new;
  580.  
  581.     new = SSquareCreate(xp, yp, xs, ys, d, parent);
  582.     SSquareDraw(new);
  583.     return new;
  584. }
  585.  
  586. SSquare *
  587. SSquareSelect(list)
  588. SSquare *list;
  589. {
  590.     int i;
  591.     SSquare *res, *which;
  592.  
  593.     /*
  594.      * If mousebutton is pressed,
  595.      * find the square in which the mouse is located and
  596.      * return that if not a leaf (pixel-sized square).
  597.      */
  598.     if (GraphicsLeftMouseEvent()) {
  599.         SuperSampleMode = 0;
  600.         if ((res = SSquareFetchAtMouse(list)) != (SSquare *)NULL)
  601.             return res;
  602.     }
  603.     else if (GraphicsRightMouseEvent()) {
  604.         SuperSampleMode = 1;
  605.         if ((res = SSquareFetchAtMouse(list)) != (SSquare *)NULL) {
  606.             return res;
  607.         }
  608.     }
  609.     if (list->closed >= SSCLOSED) {
  610.         if (Rectmode) {
  611.             Rectmode = FALSE;
  612.             RecomputePriority(SSquares);
  613.             return SSquareSelect(list);
  614.         }
  615.         return (SSquare *)NULL;
  616.     }
  617.     /*
  618.      * Otherwise, find the square with the greatest
  619.      * 'priority'.
  620.      */
  621.     res = list;
  622.     while (res && !res->leaf) {
  623.         which = (SSquare *)NULL;
  624.         for (i = 0; i < 4; i++) {
  625.             if ((res->child[i]->closed < SSCLOSED) &&
  626.                 OVERLAPS_RECT(res->child[i])) {
  627.                 which = res->child[i];
  628.                 break;
  629.             }
  630.         }
  631.         while (++i < 4) {
  632.             if ((res->child[i]->closed < SSCLOSED) &&
  633.                 which->prio < res->child[i]->prio &&
  634.                 OVERLAPS_RECT(res->child[i]))
  635.                 which = res->child[i];
  636.         }
  637.         res = which;
  638.     }
  639.     return res;
  640. }
  641.  
  642. SSquare *
  643. SSquareFetchAtMouse(list)
  644. SSquare *list;
  645. {
  646.     SSquare *res;
  647.     int x, y;
  648.  
  649.     /*
  650.      * Get mouse position.
  651.      */
  652.     GraphicsGetMousePos(&x, &y);
  653.     res = list;
  654.     while (!res->leaf && (res->closed < SSCLOSED)) { 
  655.         /*
  656.          * Find in which child the mouse is located.
  657.          */
  658.         if (x < res->child[1]->xpos) {
  659.             if (y < res->child[2]->ypos)
  660.                 res = res->child[0];
  661.             else
  662.                 res = res->child[2];
  663.         } else if (y < res->child[3]->ypos)
  664.             res = res->child[1];
  665.         else
  666.             res = res->child[3];
  667.     }
  668.     if (res->closed >= SSCLOSED)
  669.         return (SSquare *)NULL;
  670.     return res;
  671. }
  672.  
  673. SSquareDraw(sq)
  674. SSquare *sq;
  675. {
  676.     if (SQ_AREA(sq) >= MINAREA)
  677.         GraphicsDrawRectangle(sq->xpos, sq->ypos, sq->xsize, sq->ysize,
  678.             Image[sq->ypos][sq->xpos],
  679.             Image[sq->ypos][sq->xpos+sq->xsize],
  680.             Image[sq->ypos+sq->ysize][sq->xpos+sq->xsize],
  681.             Image[sq->ypos+sq->ysize][sq->xpos]);
  682.     else
  683.         DrawPixels(sq->xpos, sq->ypos, sq->xsize, sq->ysize);
  684.     if (!sq->leaf) {
  685.         SSquareDraw(sq->child[0]);
  686.         SSquareDraw(sq->child[1]);
  687.         SSquareDraw(sq->child[2]);
  688.         SSquareDraw(sq->child[3]);
  689.     }
  690. }
  691.  
  692. DrawPixels(xp, yp, xs, ys)
  693. int xp, yp, xs, ys;
  694. {
  695.     int x, y, xi, yi;
  696.  
  697.     yi = yp;
  698.     for (y = 0; y <= ys; y++, yi++) {
  699.         xi = xp;
  700.         for (x = 0; x <= xs; x++, xi++) {
  701.             SSquareSample(xi, yi, SuperSampleMode);
  702.             GraphicsDrawPixel(xi, yi, Image[yi][xi]);
  703.         }
  704.     }
  705. }
  706.